Logic Workshop

Both number theory and set theory have a claim to categoricity, in one form or another, when axiomatized in second order logic. This goes back to Dedekind and Zermelo. It is less well-known that such claims manifest themselves also in first order axiomatizations, however non-categorical such axiomatizations are in the usual setup of mathematical logic (Väänänen, 'An extension of a theorem of Zermelo' BSL, 2019). Parsons and others have written about this e.g. in Parsons, 'The uniqueness of the natural numbers' (Jerusalem Philosophical Quarterly, 1990), and Button and Walsh, 'Philosophy and Model Theory' (Oxford University Press, 2018). We claim that philosophical uses of these arguments do not carry the philosophical weight they are purported to do. To support our claim we analyse the categoricity arguments in detail in the context of both first and second order logic. We expose a common factor of such arguments, internal categoricity, namely categoricity within what the theory in question, be it number theory or set theory, can see. While internal categoricity is a remarkable phenomenon in itself, we argue that it cannot be used to defend the decidability of formal statements in the theory. In conclusion, when categoricity results are used to make certain philosophical claims, even though the categoricity results are by and large correct, they do not support those claims.

Reference: Maddy and Väänänen: Philosophical Uses of Categoricity Arguments, Elements in the Philosophy of Mathematics. Cambridge University Press. (2023).

Much work on elementary submodels of recursively saturated models of PA was done, beginning in the 1980s, by Craig Smoryński, Richard Kaye, Henryk Kotlarski, Jim Schmerl, and myself. The set of all elementary substructures of a recursively saturated model $M$ ordered by inclusion forms a lattice $Lt(M)$. Kotlarski asked whether $Lt(M)$ depends on $M$. In the talk, I will describe the architecture of $Lt(M)$, and I will survey what is known and what is still open about Kotlarski's question.

Hjorth and Thomas established that the complexity of the isomorphism problem for torsion-free abelian groups of finite rank grows dramatically higher as the rank increases: for each $r$, there is no Borel function $F$ that maps each rank-$(r+1)$ group $G$ to a rank-$r$ group $F(G)$ in such a way that $G_0\cong G_1\iff F(G_0)\cong F(G_1)$. We say that there is no Borel reduction from isomorphism on $\operatorname{TFAb}_{r+1}$ to isomorphism on $\operatorname{TFAb}_r$. (From lower to higher rank, in contrast, such a reduction is readily seen.) Fields of transcendence degree $r$ over $\mathbb Q$ have very similar computability properties to groups in $\operatorname{TFAb}_r$. This being so, we extend their investigations to include the isomorphism relations on the classes $\operatorname{FD}_r$ of such fields. We show that there do exist reductions (not merely Borel, but actually computable, and moreover functorial) from each $\operatorname{TFAb}_r$ to the corresponding $\operatorname{FD}_r$, and also from each $\operatorname{FD}_r$ to $\operatorname{FD}_{r+1}$ (which proves more challenging than it was for the groups!). It remains open whether a theorem analogous to that of Hjorth-Thomas holds for the fields, but we use the notion of countable reductions to show that the fundamental obstacle to a reduction from $\operatorname{TFAb}_{r+1}$ to $\operatorname{TFAb}_r$ is the uncountability of these spaces. This is joint work with Meng-Che 'Turbo' Ho and Julia Knight.

An object (e.g. a set, a relation, a group, etc.) is externally definable in a structure $M$ if it is given by the intersection with $M$ of an object definable (with parameters) in some elementary extension of $M$. If all types over $M$ are definable (for example, if the theory of $M$ is stable), then all externally definable sets are already definable. This fails beyond stability, e.g. in linear orders (take a cut of some irrational number over the rationals) or in the Rado graph (where all subsets of a model are externally definable). An important theorem of Shelah shows that at least the expansion of an NIP structure $M$ by all externally definable sets $M^{\text{ext}}$ remains NIP. While externally definable sets in NIP structures are well behaved, partially explained by the existence of 'honest definitions' introduced in joint work with Simon, many questions remain open. In this talk I will survey some topics in the study of externally definable sets and discuss some new results on externally definable groups in NIP structures.

Last semester, I discussed geometric methods for decidability over a complete discrete valuation ring (DVR) in equal characteristic, suggesting that these methods could be applied effectively. In this talk, I aim to clarify the computability issues surrounding this topic while at the same time shifting focus to the case of mixed characteristic. Whereas quantifier elimination (QE) results are established for p-adic numbers, the general landscape remains less explored. I will demonstrate that for any existential sentence over a computable ring, we can effectively construct a positive existential (or Diophantine) sentence which is logically equivalent to the original in every excellent Henselian DVR containing the ring. This construction hinges on Resolution of Singularities, which is feasible in characteristic zero.

Furthermore, I will utilize ultraproducts, specifically the protoproduct variant, to show how Diophantine statements over a DVR can be reduced to those over a residue ring. Since the residue ring is Artinian—and in the case of p-adics, even finite—the associated problems become significantly more manageable. However, it is important to note that this approach does not yet yield a general QE result, as it applies only to sentences, not formulas. The challenge lies in the dependence of certain effective bounds on parameters. I will provide insights into how to derive a bound based on a refined notion of complexity within the equational system—beyond simply considering its degree—using ultraproducts. Additionally, I will address a request from the audience in my last talk by demonstrating that this bound is indeed effective.

And somehow it will also require some delving into the theory of Witt vectors and ancient elements, as I will explain.

An Abelian lattice-ordered group (l-group) is an Abelian group with a lattice order that is invariant under translations. Examples include $C(X)$, the set of continuous real-valued functions on a topological space $X$ with pointwise operations and order, the $L_p$ spaces, and certain spaces of measures. After surveying some of the known decidability results for various classes of l-groups, I will present new decidability results concerning existentially closed l-groups.

Measurable cardinals and other large cardinals on the larger side of things are characterized by the existence of elementary embeddings $j:V\to \mathcal M$ from the universe $V$ of sets into a transitive submodel $\mathcal M$. The clear pattern the large cardinals in that region follow is that the closer the submodel $\mathcal M$ is to $V$ the stronger the large cardinal notion. Smaller large cardinals, such as weakly compact or Ramsey cardinals, are known chiefly for their combinatorial properties, such as the existence of large homogeneous sets for colorings. But, it turns out that they too have elementary embeddings characterizations with embeddings on the correspondingly small models $M$ of (a fragment) of set theory (usually ${\rm ZFC}^-$, the theory ${\rm ZFC}$ with powerset axiom removed). Elementary embeddings of $V$ are often by-definable with the existence of certain ultrafilters or systems of ultrafilters. The classical example is that $\kappa$ is measurable if and only if there is a $\kappa$-complete ultrafilter on $\kappa$. The model $\mathcal M$ is then the transitive collapse of the ultrapower of $V$ by $U$. The connection between elementary embedding and ultrafilters also exists in the case of the small elementary embeddings. A typical elementary embedding characterization of a small large cardinal $\kappa$ follows the following template: for every $A\subseteq\kappa$, there is a (technical condition) model $M$, with $A\in M$, for which there is an $M$-ultrafilter $U$ on $\kappa$ with (technical properties). A subset $U\subseteq P(\kappa)\cap M$ is an $M$-ultrafilter if the structure $\langle M,\in, U\rangle$, with a predicate for $U$, satisfies that $U$ is a $\kappa$-complete ultrafilter on $\kappa$, meaning that $U$ measures all the sets in $M$ and its completeness applies to sequences that are elements of $M$. The reason we need to add a predicate for $U$ is that in most interesting case, and in contrast to the situation with measurable cardinals, $U$ is not an element of $M$ (indeed in most cases, $P(\kappa)$ does not exist in $M$). While the structure $M$ usually satisfies some large fragment of ${\rm ZFC}$, once, we add a predicate for the $M$-ultrafilter $U$, the structure $\langle M,\in, U\rangle$ can fail to satisfy even $\Sigma_0$-separation. In this talk, I will discuss how smaller large cardinals follow the pattern that the more set theory the structure $\langle M,\in, U\rangle$ satisfies the stronger the resulting large cardinal notion. I will use these observations to introduce a new hierarchy of large cardinals between Ramsey and measurable cardinals. This is joint work with Philipp Schlicht, based on earlier work by Bovykin and McKenzie.

Shelah showed that it is consistent that there are uncountable rigid non-archimedean real closed fields and, later, he and Mekler proved this in $\textbf{ZFC}$. Answering a question of Enayat, Charlie Steinhorn and I show that there are countable rigid non-archimedean real closed fields by constructing one of transcendence degree two.

(One version of) Cantor's second best theorem states that every pair of countable, dense sets of reals are isomorphic as linear orders. From the perspective of set theory it's natural to ask whether some variant of this theorem can hold consistently when 'countable' is replaced by 'uncountable'. This was shown in the affirmative by Baumgartner in 1973 who showed the consistency of 'all $\aleph_1$-dense sets of reals are order isomorphic' where a set is $\kappa$-dense for a cardinal $\kappa$ if its intersection with any open interval has size $\kappa$. The above became known as Baumgartner's axiom, denoted BA, and is an important axiom in both combinatorial set theory and set theoretic topology. BA has natural higher dimensional analogues - i.e., statements with the same relation to $\mathbb R^n$ that BA has to $\mathbb R$. It is a long standing open conjecture of Steprāns and Watson that BA implies its higher dimensional analogues.

In the talk I will describe some attempts to break the ice on this open problem mostly by looking at a family of weaker and stronger variants of BA and investigating their combinatorial, analytic and topological consequences. We will show that while some weak variants of BA have all the same consequences as BA, even weaker ones do not. Meanwhile a strengthening of BA for Baire and Polish space gives much more information.